package Hard;

import java.util.*;

// 757. 设置交集大小至少为2
public class Solution757 {
    public int intersectionSizeTwo(int[][] intervals) {
        /*
            用all记录当前所有满足条件的大小至少为2的交集（这些集合大小相同）
            每增加一个interval后，为了维护上面这条原则，我们需要：
            首先，获得新的interval的所有大小为2的子集，
                更新all：如果考虑新的interval以后，all里当前这个集合不为答案，则更新该集合使得满足条件
                维护all，使得all里所有集合大小相同（取最小）
            ------------
            结论：不行，这个思路不对
        */
        List<Set<Integer>> all = new ArrayList<Set<Integer>>();
        int min = 2;
        for(int i = intervals[0][0] ; i <intervals[0][1] ; i++){
            Set<Integer> integer = new TreeSet<Integer>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1 - o2;
                }
            });
            integer.add(i);
            integer.add(i+1);
            all.add(integer);
        }
        for(int i = 1 ; i < intervals.length ; i++){
            int start = intervals[i][0];
            int end = intervals[i][1];
            int newMin = min;
            boolean flag = false;
            for(int j = 0 ; j < all.size() ; j++){
                Set<Integer> preInteger = all.get(j);
                if(findMin(preInteger)>=start && findMax(preInteger) <= end){
                    newMin = min;
                    flag = true;
                    continue;
                }else if(findMin(preInteger) < start && findMax(preInteger) > end){
                    newMin = min;
                    flag = true;
                    continue;
                }else if(findMin(preInteger) < start){
                    preInteger.add(start);
                    preInteger.add(start+1);
                    // all.set(j,preInteger);
                    if(flag){
                        newMin = Math.min(newMin,preInteger.size());
                    }else{
                        newMin = preInteger.size();
                        flag = true;
                    }
                }else if(findMax(preInteger) > end){
                    preInteger.add(end);
                    preInteger.add(end - 1);
                    // all.set(j,preInteger);
                    if(flag){
                        newMin = Math.min(newMin,preInteger.size());
                    }else{
                        newMin = preInteger.size();
                        flag = true;
                    }
                }
            }
            for(int j = 0 ; j < all.size() ; j++){
                Set<Integer> preInteger = all.get(j);
                int distance = preInteger.size();
                if(distance > newMin){
                    all.remove(j);
                    j--;
                }
            }
            min = newMin;
        }
        return min;
    }
    public static int findMin(Set<Integer> set){
        Object[] objects = set.toArray();
        return (int)objects[0];
    }
    public static int findMax(Set<Integer> set){
        Object[] objects = set.toArray();
        return (int)objects[objects.length-1];
    }
}
